/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package ga_checkpoint_3;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/**
 *
 * @author Asif Dipon, Harshal Joshi
 */
public class Main {

    //constant static variables that define the max number of generations the
    //algorithm should run for and the range in which the entity's chromosomes
    //may fall under
    final static int MAX_NUM_GENERATION = 100;
    final static int MAX_POP_SIZE = 10;
    final static int RANGE_MAX = 500;

    /**The main method. It processes command line arguments and starts the
     * primary program.
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        doTask();
    }

    /**
     * This runs the algorithm. It creates the 0th generation. Then it spawns 10
     * new generations through crossover and mutation. At each generation, the 10
     * fittest entities survive to live into the next generation.
     */
    public static void doTask(){
        //Create the 0th generation with random values.
        List<TourPath> population = createGenZero();
        int genNum = 0;
        //Print the info for the 0th generation.
        printInfo(population, genNum);
        //Create new generations until the limit is reached.
        while(genNum < MAX_NUM_GENERATION){
            //Create a list of child entities that will be created through crossover and mutation
            List<TourPath> spawn = new ArrayList<TourPath>();
            //Do crossover and mutation 5 times each
            for( int i = 0; i<5; i++){
                //create spawn through crossover
                TourPath p1 = selectRandomFromPopulation(population);
                TourPath p2 = selectRandomFromPopulation(population);
                TourPath child1 = doCrossover(p1, p2);
                spawn.add(child1);
                //create spawn through mutation
                TourPath p3 = selectRandomFromPopulation(population);
                TourPath child2 = doMutation(p3);
                spawn.add(child2);
            }
            //add all spawn to the population
            population.addAll(spawn);
            //Sort the population based on fitness, in ascending order.
            Collections.sort(population);
            //select top 10 fittest in the population
            int size = population.size();
            List<TourPath> top10 = new ArrayList();
            for(int i=0; top10.size()<MAX_POP_SIZE && i<population.size(); i++){
                TourPath temp = population.get(i);
                if(!top10.contains(temp)){
                    top10.add(temp);
                }
            }
            //Remove all entities in the population that are not in the top10.
            population.clear();
            for(TourPath e: top10){
                population.add(e);
            }
            //Print the info for the generation
            genNum++;
            printInfo(population, genNum);

        }

        //At the end of the run, print the info for the best path.
        TourPath best = population.get(0);
        System.out.println("\n\nBest path\nId=" + best.id + "\nTour Path=" + best);
    }

    /**
     * This method creates generation 0 through random assignment of chromosomes.
     * @return A list containing 10 randomly generated entities.
     */
    public static List<TourPath> createGenZero(){
        List<TourPath> population = new ArrayList<TourPath>();
        //Generate a list of random cities
        List<City> cityList = getRandomCities(10);
        printCityList(cityList);
        Random rand = new Random();
        //Create random tour paths of the cities to fill up the population
        for(int i =0; i<MAX_POP_SIZE; i++){
            int uid = UIDGen.getInstance().getNextUID();
            TourPath e = new TourPath(uid);
            for(int j=0; j<cityList.size(); j++){
                //Add the current city to a random location in the list.
                e.tour.add(rand.nextInt(e.tour.size()+1), cityList.get(j));
            }
            population.add(e);
        }
        return population;
    }

    /**
     * Creates cities with random coordinates.
     * @param size  The total number of cities to create.
     * @return  A list containing all the cities.
     */
    private static List<City> getRandomCities(int size) {
        Random rand = new Random();
        List<City> cityList = new ArrayList<City>();
        for(int i= 0; i<size; i++){
            int x = rand.nextInt(RANGE_MAX + 1);
            int y = rand.nextInt(RANGE_MAX + 1);
            char id = (char)('A' + i);
            City c = new City(id, x, y);
            cityList.add(c);
        }
        return cityList;
    }

    /**
     * This method takes two parent entities and creates a child entity
     * through crossover of genes.
     * @param parent1   The first parent to take genes from.
     * @param parent2   The second parent to take genes from
     * @return  A new child entity
     */
    public static TourPath doCrossover(TourPath parent1, TourPath parent2){
    	TourPath child = new TourPath(UIDGen.getInstance().getNextUID());
    	Random rand = new Random();
        //Select a random point in the first parent to split at.
        int splitter = rand.nextInt(parent1.tour.size());
        child.tour.addAll(parent1.tour.subList(0, splitter));
        //fill up the remaining slots in the child with unique cities from parent2's
        //path in the order they appear.
        for(City c:parent2.tour){
            if(!child.tour.contains(c)){
                child.tour.add(c);
            }
        }
    	return child;
    }

    /**
     * This method creates a child entity through the mutation of one or more
     * genes of a parent entity.
     * @param parent    The entity whose genes will mutate
     * @return  A child entity that is different from its sole parent
     */
    public static TourPath doMutation(TourPath parent){
    	//choose two random indexes that are unique
    	Random rand = new Random();
       	int randNum = 0;
        int randNum2 = 0;
        while (randNum == randNum2){
            randNum = rand.nextInt(parent.tour.size());
            randNum2 = rand.nextInt(parent.tour.size());
        }
        //Create a child tour path based on the parent provided.
       	TourPath child = new TourPath(UIDGen.getInstance().getNextUID());
        child.tour.addAll(parent.tour);
        //Swap the child's cities at the selected indexes.
        child.tour.set(randNum2, parent.tour.get(randNum));
        child.tour.set(randNum, parent.tour.get(randNum2));
        //Return the newly created child city.
        return child;
    }    

    /**
     * Prints the list of cities given
     * @param cityList  The list of cities.
     */
    public static void printCityList(List<City> cityList){
        System.out.println("\nCity List");
        System.out.println("CityID\tXCor\tYCor");
        for(City c: cityList){
            System.out.println("" + c.id + "\t\t" + c.xcor + "\t\t" + c.ycor);
        }
    }

    /**
     * This method prints the relevant information for each generation: generation
     * number, the min/max fitness, and the population's information.
     * @param population    The list containing the population.
     * @param genNum    The generation number
     */
    public static void printInfo(List<TourPath> population, int genNum){
        //Print the generation number
        System.out.println("\n\nGeneration #" + genNum);
        //Sort the population
        Collections.sort(population);
        //Print out the min and max fitness among the population
        System.out.println("\nMin fitness: " + population.get(0).getFitness());
        System.out.println("Max fitness: " + population.get(population.size()-1).getFitness());
        //Print out each individual in the population and their information.
        System.out.println("\nID \t\t Fitness \t\t\t Path");
        for(TourPath e : population){
            System.out.print("\n" + e.id + " \t " + e.getFitness() + " \t " + e);
        }
        System.out.println();

    }

    /**
     * Returns a pseudorandom member from a population
     * @param pop
     * @return
     */
    public static TourPath selectRandomFromPopulation(List<TourPath> pop){
        Random rand = new Random();
        int index = rand.nextInt(pop.size());
        return pop.get(index);
    }

    /**
     * Returns a random double between the ranges specified.
     * @param rangeMin  The lower bound
     * @param rangeMax  The upper bound
     * @return  A pseudorandom double within the specified range.
     */
    public static double getRandomDouble(double rangeMin, double rangeMax){
        double retVal = 0;
        Random rand = new Random();
        retVal = ((rangeMax-rangeMin) * rand.nextDouble()) + rangeMin;
        return retVal;
    }
}
